package com.liu.algorithm.search.binary;

/**
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 * 有序数组+搜索值
 */
public class Leetcode704 {
    public static void main(String[] args) {
//        int[] nums = {-1, 0, 3, 5, 9, 12};
//        int target = 9;

//        int[] nums = {-1, 0, 3, 5, 9, 12};
//        int target = 2;
        int[] nums = {-1, 0, 5};
        int target = -1;
        Leetcode704 obj = new Leetcode704();
        int index = obj.search(nums, target);
        System.out.println(index);
    }

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int index = (left + right) / 2;
            if (target > nums[index]) {
                left = index + 1;
            }
            else if (target < nums[index]) {
                right = index - 1;
            }
            else {
                return index;
            }
        }
        return -1;
    }

    public int search(int[] nums, int target, int startIndex, int endIndex) {
        System.out.println(startIndex + "~" + endIndex);
        int index = (startIndex + endIndex) / 2;
        int data = nums[index];
        if (data > target) {
            endIndex = index;
        }
        else {
            startIndex = index;
        }
        if (data == target) {
            return index;
        }
        if (endIndex < startIndex || target < nums[startIndex] || target > nums[endIndex]) {
            return -1;
        }
        if (startIndex + 1 == endIndex) {
            if (target == nums[startIndex]) {
                return startIndex;
            }
            else if (target == nums[endIndex]) {
                return endIndex;
            }
            else {
                return -1;
            }
        }
        return search(nums, target, startIndex, endIndex);
    }
}
